'lintcode 排列序号'

Posted on | In

lintcode 排列序号

描述

给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

样例

例如，排列 [1,2,4] 是第 1 个排列。

思路

排列一共有n!种,最高位定下来之后一共是n个(n-1)!种排列,根据这种性质,可以通过查找低位比高位小的个数来计算当前位置.
比如,1247的排列个数是4!个.寻找2174的位置.
首选从最高位的2开始,后面比他小的只有1个,所以他前面肯定有1开头排列的3!=6个.
然后比较1,没有.
然后比较7,只有1个,此时只剩下两位数,所以74之前只有1个47.
这样得到的最后结果应该是1+6+1=8.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    /**
     * @param A: An array of integers
     * @return: A long integer
     */
    long long permutationIndex(vector<int> &A) {
        // write your code here
        int n = A.size();
        long long res = 1;
        long long temp = 1;
        for (int i = 2; i < n; i++)
            temp *= i;
        for (int i = 0; i < A.size()-1; ++i) {
            int t = 0;
            for (int j = i+1; j < A.size(); j++) {
                if (A[i] > A[j])
                    t++;
            }
            res += temp * t;
            --n;
            temp /= n;
        }
        return res;
    }
};
-------------end of filethanks for reading-------------